package com.likou.second_challenge;

public class q53 {


    public int maxSubArray(int[] nums) {

        int ans = Integer.MIN_VALUE;
        int n = nums.length;
        int sum = 0;

        for (int num : nums) {
            sum = Math.max(sum + num, num);
            ans = Math.max(sum, ans);
        }

        return ans;
    }


//    public int maxSubArray(int[] nums) {
//
//        int ans = Integer.MIN_VALUE;
//        int n = nums.length;
//        int sum = 0;
//
//        for (int num : nums) {
//            if (sum < 0) {
//                sum = 0;
//            }
//            sum += num;
//
//            ans = Math.max(ans, sum);
//        }
//
//        return ans;
//    }

    // 暴力
//    public int maxSubArray(int[] nums) {
//
//        int ans = Integer.MIN_VALUE;
//        int n = nums.length;
//
//        for (int i = 0; i < n; i++) {
//            int temp = 0;
//            for (int j = i; j < n; j++) {
//                temp += nums[j];
//                ans = Math.max(temp, ans);
//            }
//        }
//
//        return ans;
//    }

}
